A list is a sequence of elements. A sorted list is a list that is sorted according to a particular sorting priority (such as alphabetical, increasing value, and so forth). A sorted list guarantees that for every pair of consecutive elements, the previous element satisfies the particular sorting priority with respect to the subsequent element. For instance, suppose that the list includes a sequence of integers, and that the sorting priority is an increasing value sorting priority. In that case, the list of integers would be sorted according to increasing value if for every pair of consecutive integer in the sequence, the subsequent integer is equal to or greater than the previous integer. Each sorted list includes a head element, which is the highest priority in the sorting priority, and thus the first element in the sorted list. Each sorted list also includes a tail element, which is a lowest priority in the sorting priority, and thus the last element in the sorted list.
There is a particular method (referred to herein as a “priority queue method”) that was developed a number of decades ago to merge input sorted lists into a merged sorted list that is sorted according to the same sorting priority as the input sorted lists. This priority queue method uses a priority queue in order to formulate a merged list, and involves multiple phases of sorting operation. In the first phase, each of the head elements from all of the input sorted lists are placed in the priority queue, and thus each space in the priority queue corresponds to an input sorted list. In each sorting phase, the merged sorted list is extended by one element by moving the highest priority element that is within the priority queue to the end of the merged sorted list as a new tail element of the merged sorted list. The highest unprocessed priority element from the input sorted list corresponding to the space vacated by this move is then processed by copying the element into vacated space, thus completing a sorting phase.